from typing import *


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        mx = 10**6
        primes = []
        isPrime = [True] * (mx + 1)
        isPrime[0], isPrime[1] = False, False
        mxFactors = [1] * (mx + 1)
        for i in range(2, mx + 1):
            if isPrime[i]:
                primes.append(i)
            for p in primes:
                if i * p > mx:
                    break
                isPrime[i * p] = False
                mxFactors[i * p] = i
                if i % p == 0:
                    break
        ans = 0
        for i in range(len(nums) - 2, -1, -1):
            while nums[i] > nums[i + 1] and mxFactors[nums[i]] != 1:
                nums[i] //= mxFactors[nums[i]]
                ans += 1
            if nums[i] > nums[i + 1]:
                return -1
        return ans
